1650G - Counting Shortcuts - CodeForces Solution

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

const int MN = 200005;
const int MOD = 1000000007;

int dis[MN];
int dp[2][MN];
vector <int> adj[MN];
int vis[2][MN];

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int Tc; cin >> Tc;
	while (Tc --) {
		int n, m, s, e; cin >> n >> m >> s >> e;
		s --; e --;
		for (int i = 0; i < n; i ++) adj[i].clear();
		for (int i = 0; i < m; i ++) {
			int u, v; cin >> u >> v;
			u --; v --;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		for (int i = 0; i < n; i ++) {
			dp[0][i] = dp[1][i] = 0;
			vis[0][i] = vis[1][i] = 0;
			dis[i] = -1;
		}
		queue <pair<int, int> > Q;
		Q.push({0, s}); dis[s] = 0; dp[0][s] = vis[0][s] = 1;
		while (!Q.empty()) {
			int f = Q.front().first, u = Q.front().second; Q.pop();
			for (auto v : adj[u]) {
				if (dis[v] < 0 || dis[u] + f <= dis[v]) {
					if (dis[v] < 0 || dis[u] + f < dis[v]) {
						dis[v] = dis[u] + 1 + f;
						dp[0][v] += dp[f][u];
						dp[0][v] %= MOD;
						if (!vis[0][v]) Q.push({0, v});
						vis[0][v] = 1;
					}
					else {
						dp[1][v] += dp[f][u];
						dp[1][v] %= MOD;
						if (!vis[1][v]) Q.push({1, v});
						vis[1][v] = 1;
					}
				}
			}
		}
		cout << (dp[0][e] + dp[1][e])% MOD << endl;
	}

	return 0;
}